COMMENT ⊗   VALID 00006 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00003 00002	2. WHAT WE PROPOSE TO DO.
C00009 00003		The micro language  is composed of  a small set  of primitive
C00016 00004		Besides language inputs,  a  geometric modeling system should
C00022 00005	WHAT WE PROPOSE TO DO  -  An Itemized Shopping List.
C00025 00006
C00026 ENDMK
C⊗;
2. WHAT WE PROPOSE TO DO.

	We  propose to  represent  and simulate  solid  objects in  a
computer  for the sake  of mechanical design  and mechanical drawing.
Our two year goal  will be to automate as  much as possible the  task
of  creating  and altering  three  dimensional  data structures  from
which  mechanical drawings  can  be derived.  The overall  project to
date has  been called  "geometric modeling" a  term which  we use  to
refer to  our particular combination of computer  graphics,  physical
world modeling,   image processing  and geometry.   Accordingly,  the
details of the  work we propose doing  will be presented in  terms of
the elements comprising a Geometric Modeling System,  GMS.

	Like  a computer,    the four  main elements  of  a geometric
modeling system are memory, process, input and output.  Starting with
memory, there are  the problems of representation (how  to describe a
physical object);  accessing (how to find a particular description by
name,   by location,  or by  whether it  is currently  in view);  and
efficiency (how  to keep the  size of storage  space down and  how to
dynamically allocate fast and slow memory resources).
	
	The presently  implemented explicit object  representation is
based on  polyhedron models of solid rigid  objects.  A simple object
called a body  is defined by  a surface  shell composed of  vertices,
edges and  faces that satisfies the  Euler equation, V  - E + F  = 2;
such  polyhedron bodies  are combined to  form compound  objects.  At
present,  curved objects are represented by  approximating them using
a  polyhedron  composed of  a  sufficient  number  of flat  polygonal
faces.   We propose  to  further develope  the appearance  of  curved
objects by automating the  assignment of polygonal facets to  a given
curved  surface.   Other  current  representation  problems  that  we
propose working on  include constructing  efficient (and  compatible)
object  labeling, handling  mechanical properties  of an  object, and
better representing compound and flexible objects.

	A final  representation issue  we would  study is  that of  a
format   for  communication  of  three   dimensional  models  between
modeling systems.   Although,   we believe  that it is  too early  to
propose a standard  format; it is desirable to  design and promulgate
a  format as  simple, but as  inclusive as  possible; and  it is also
desirable to  develope formatible  I/O routines so  that new  formats
can be sent or received.

	The  usual  input  devices  to  a geometric  modeling  system
include keyboards,  light-pens,   joy-sticks,  buttons,  cameras  and
film scanners; of  which the most  important to this proposal  is the
keyboard because it  is currently the best device for language input.
Indeed, we believe  that we can  demonstrate that  a system based  on
keyboards can do  geometric control and editing better  than a system
based on  both a light pen and a keyboard.  With respect to language,
we are proposing two projects: first, we would  extend the programing
languages: FORTRAN,   ALGOL and LISP; and second,   we would continue
to develope our interactive edit  and control language. The  elements
of a language extension  include new data types (the  "memory" of our
system);  a  micro  language  of  primitive  operations and  a  macro
language of more complex operations.

	The micro language  is composed of  a small set  of primitive
functions  that  invoke  the  only  subroutines  allowed to  directly
create and alter  the data structure.  All the geometric  processors,
editors,  input,     output   and  higher  language   operations  are
implemented  in  terms of  these fewer  than  fifty primitives.   The
reason for having a two  level system is to isolate and  minimize the
amount of  code that is  necessarily dependent on  the implementation
details of the particular higher  level language. Furthermore, it  is
possible to construct  primitives that are complete and  general with
respect   to  fundamental  principles  in   polyhedron  topology  and
geometry. For example,   we now have a  set of Euler primitives  that
can generate  any Eulerian polyhedron (and  only Eulerian polyhedra);
as  well as a set  of Euclidean primitives for  applying the group of
Euclidean  transformations.  With more  good  luck,    we  intend  to
isolate sets of primitives for mechanics and for image formation.

	The  macro  level  of  language  extension  is  comprised  of
operations that make  it convenient to simulate building a mechanical
model of an  object. The  present macro level  includes an  operation
for  "sweeping"  edges  into  faces,    and  faces  into  solids;  an
operation  for "glueing" surfaces together;  an operation for passing
"cutting"  planes  thru an  object;  and  a  most  powerful  trio  of
operations   for  forming  the   volume  union,     intersection  and
difference of two given  polyhedra. Since polyhedra  can be taken  as
either bounding a  finite solid volume  or a finite empty  volume; we
have found it  convenient to draw some objects indirectly by building
their holes  and  intersecting  the  holes with  their  simple  outer
shape.   Further macro  operations we propose  to code  would include
more   "imaginery"   ones  for   bending,     constraining,  filling,
enveloping, and  expanding  upon a  skeleton; as  well  as some  more
"realistic"  operations that would  model regular machine  shop tools
such as  a lathe,   punch  and milling  machine; as  well as  machine
building processes such as welding, fastening and assembly. 

	Our second  language project  is oriented towards   edit  and
control.    The  main  differences  between  an interactive  graphics
editor and a graphics programming language is that an  editor carries
along its  working context  so that  most arguments  and data  do not
have to  be explicitly named because they happen to be "at the top of
the stack" and are visibly intensified or otherwise  indicated on the
display screen.  The advantage of the interactive  editor is that the
user is relieved of having to coin and call names of things,  however
the disadvantage  is  that he  can not  develope  subroutines of  the
power  available in  a programming  language which  provides notation
for  procedures, arguments,  and  variables.  We  plan  to  keep  the
programming  language  level  distinct  from  the  control  and  edit
language  level;  although  it should  be  clear  that  both language
levels are calling the same primitive execution routines.
	Besides language inputs,  a  geometric modeling system should
have  a way of  reading data that  is already in  graphical form. For
such input,  we propose using  a television camera. For example,   we
already have developed video  intensity contouring to rapidly provide
the  edges of  an  image in  a form  available for  graphics editing.
Although video  input  per  se is  of  secondary importance  to  this
proposal,  we happen to  have such hardware and software available at
Stanford and can make good use  of it with little additional  effort.
Furthermore,   video  (or  visual)  computer input  has  considerible
promise as a major input device of future computers.

	The third  element  of a  geometric modeling  system are  its
(software)  processors.  There  are language  processors,  mechanical
simulators,  locus solvers,  image analysis and image synthesis,   as
well  as that  process  quite central  to  three dimensional  drawing
which  is hidden line  (and surface)  elimination.  We  have a hidden
line eliminator  which combines  several of  the existing  techniques
and which can  generate both line drawings and  video images; also we
have reason to believe that further  work on our design will yield  a
hidden  eliminator  that   can  handle  apparently   curved  objects,
generate shadows,  use the coherence between  successive images,  and
still be fast  without special purpose hardware.   Since the  purpose
of  the processors  just mentioned  should be  sufficiently clear  we
shall  skip detailing  their algorithms  and implementation, although
this will comprise  the bulk of the  work and publication we  propose
to do.

	The fourth and  final element of  our modeling system  is the
output,    which  includes  dynamic  CRT  display,    video  display,
hardcopy printing, as well as  magnetic tape. Although mundane,   the
numerical object descriptions on  conventional (non display) computer
media  like magnetic  tape is  important in  making the output  of an
interactive   display  system   available   for   further   automatic
processing or  communication. On the  other hand, a  high quality CRT
that can display characters and vectors  is now and shall remain  the
primary tool  requiste to  developing interactive graphics  software;
consquently nearly  a half of the budget  included with this proposal
is allocated to aquiring such  a CRT to enhance our existing  display
system. The most  promising alternative to a CRT is  a video display;
however present  day video display systems would require a very large
computer and fast  memory to  achieve the resolution  and speed of  a
CRT display.
WHAT WE PROPOSE TO DO  -  An Itemized Shopping List.

	Ignoring the overall system organization and fine details,
the goals of the proposed project are summarized in the following
shopping list:

Items partially in hand.

	1. Representation of solid rigid three dimensional polyhedra.
	2. Language extension of geometric primitives.
	3. Language extension of object building operations.
	4. Polyhedron object hidden line (and surface) eliminator.
	5. Geometric editor.

Items within one year's work.
	
	6. Generation of mechanical drawings from geometric models.
	7. Representation for the appearance of curved objects.
	8. Representation for flexible objects.
	9. Video acquisition of two dimensional  drawings.
	10. Mechanical simulation and animation.

Second year and/or elective Items.

	11. Generation of high quality mechanical drawings.
	12. Development of a remote display terminal version.
	13. Development of a standard FORTRAN version.
	14. Mechanical drawings for a special area of engineering;
	    (pipefitting, screw threading, mining, or whatever).

Basic research items.

	15. Video acquisition of three dimensional objects.
	16. Photometric simulation - shadows, multiple light sources;
	    for generation of high quality video appearance.

	The most conservative estimate of  our potential achievements
for  the next two  years would include  the first  five items listed,
since  substantial   work  has   already  been   done.   Intermediate
expectations would include making  considerable progress and original
contribution  with respect to the  items one through  ten; as well as
doing  one  of the  five  items  numbered  eleven  through  fourteen.
Optimistic  expectation would  be  to finish  everything  though item
sixteen.